<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        //DFS回溯法
        /* var isInterleave = function (s1, s2, s3) {
            //1.判断长度
            //2.统计s1,s2每个字符出现的次数
            //3.统计s3每个字符出现的个数，是否为s1+s2
            //4.还要判断s1 s2的字符串顺序在s3中是否被打乱
            //234连在一起可以不用计算字数了，如果匹配，则子串和总串的指针向后移
            if (s3.length != (s1.length + s2.length))
                return false
            const check = function (i, j, k) {
                if (k === s3.length) return true
                let isValid = false
                if (i < s1.length && s1[i] === s3[k]) { //如果匹配，则s1和s3的指针向后移
                    isValid = check(i + 1, j, k + 1)
                }
                if (j < s2.length && s2[j] === s3[k]) { //如果匹配，则s2和s3的指针向后移
                    isValid = isValid || check(i, j + 1, k + 1)
                }
                return isValid
            }
            return check(0, 0, 0)
        };
        console.log(isInterleave('aabcc', 'dbbca', 'aadbbbaccc')) */
        //试试DP法
        var isInterleave = function (s1, s2, s3) {
            let len1 = s1.length,
                len2 = s2.length,
                len3 = s3.length
            if (len1 + len2 != len3) return false
            let dp = Array.from(new Array(len1 + 1), () => new Array(len2 + 1))
            dp[0][0] = true
            for (let i = 1; i <= len1; i++) {
                dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1]
            }
            for (let i = 1; i <= len2; i++) {
                dp[0][i] = dp[0][i - 1] && s2[i - 1] == s3[i - 1]
            }
            for (let i = 1; i <= len1; i++) {
                for (let j = 1; j <= len2; j++) {
                    dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[i +
                        j - 1])
                }
            }
            console.log(dp)
            return dp[len1][len2]
        }
        console.log(isInterleave('aabcc', 'dbbca', 'aadbbbaccc'))
        console.log(isInterleave('aabcc', 'dbbca', 'aadbbcbcac'))
    </script>
</body>

</html>